#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-20 6:36 下午
# @Author  : yangdy
# @File    : 2020-07-19.
# @Software: PyCharmCE
from functools import lru_cache
from typing import List


class SolutionCache:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        val = [1] + nums + [1]
        # 缓存函数结果，记忆化搜索。。。
        @lru_cache(None)
        def solve(left: int, right: int) -> int:
            if left >= right - 1:
                return 0

            best = 0
            for i in range(left + 1, right):
                total = val[left] * val[i] * val[right]
                total += solve(left, i) + solve(i, right)
                best = max(best, total)

            return best

        return solve(0, n + 1)


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        ans = 0
        ln = len(nums)
        dp = [[0 for i in range(ln+1)] for j in range(ln)]
        print('dp', dp)
        # for l in range(1, 1 + 2):
        for l in range(1, ln+1):
            for i in range(ln):
                print(l, i)
                for j in range(i, min(i+l, ln)):
                    print(' ', l, i, j)
                    x = nums[j] * (nums[j-1] if j > i else 1) * (nums[j+1] if j < i+l-1 and j < ln-1 else 1)
                    print(' ', i, j-i, j, l-j+i, x)
                    # dp[i][l] = max(dp[i][l], dp[i][j-i] + x + dp[j][l-j+i])
                    dp[i][l] = max(dp[i][l], dp[i][j - i] + x + (dp[j+1][l - j + i - 1] if j < i+l-1 and j < ln-1 else 0))
                    print(dp)
        print(dp)
        return ans


solve = Solution()

questions = [
    ([3, 1, 5, 8], ),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.maxCoins(q[0]))
